﻿#include <iostream>
#include <stack>
#include "Graph.h"

static void search(const Graph* graph, GraphNode* startNode)
{
    unordered_set<GraphNode*> appearNodes;
    stack<GraphNode*> nodeStack;
    nodeStack.push(startNode);
    appearNodes.insert(startNode);
    printf("%c->", startNode->value);

    while (!nodeStack.empty())
    {
        auto topNode = nodeStack.top();
        nodeStack.pop();
        for (auto nodeIterator = topNode->nextNodes.begin(); nodeIterator != topNode->nextNodes.end(); nodeIterator++)
        {
            auto nextNode = *nodeIterator;
            if (appearNodes.find(nextNode) == appearNodes.end())
            {
                nodeStack.push(topNode);
                nodeStack.push(nextNode);
                appearNodes.insert(nextNode);
                printf("%c->", nextNode->value);
                break;
            }
        }
    }

    printf("\n");
}

// 递归遍历
static void recurSearch(const Graph* graph, GraphNode* startNode, unordered_set<GraphNode*>& appearNodes)
{
    if (appearNodes.end() != appearNodes.find(startNode)) return;

    printf("%c->", startNode->value);
    appearNodes.insert(startNode);
    for (auto nodeIterator = startNode->nextNodes.begin(); nodeIterator != startNode->nextNodes.end(); nodeIterator++)
    {
        recurSearch(graph, *nodeIterator, appearNodes);
    }
}

// 深度优先遍历
int main_DepthFirstSearch()
{
    int matrix[][3] = {
        {'a', 'b', 3},
        {'a', 'c', 15},
        {'a', 'd', 9},
        {'b', 'c', 2},
        {'b', 'e', 200},
        {'c', 'd', 7},
        {'c', 'e', 14},
        {'d', 'e', 16},
    };

    int* pMatrix = matrix[0];
    auto graph = Graph::generate(&pMatrix, sizeof(matrix) / sizeof(int) / 3, 3, false);
    search(graph, graph->nodes.at('a'));

    unordered_set<GraphNode*> appearNodes;
    recurSearch(graph, graph->nodes.at('a'), appearNodes);
    printf("\n");

    delete(graph);
    return 0;
}